home *** CD-ROM | disk | FTP | other *** search
/ 9-Digit Zip Code Directory / 9-Digit Zip Code Directory (American Business Information) (ABIZIP-12).ISO / z4src.zip / CPRECID.C < prev    next >
C/C++ Source or Header  |  1993-07-06  |  13KB  |  486 lines
  1. //----------------------------------------------------------------------------
  2. //                            MODULE DESCRIPTION
  3. //
  4. //  Module:    cprecid.c
  5. //   Title:    Data Compression Library
  6. //  Notice:    John M. Weeder
  7. //                 Copyright (c) 1993. All rights reserved.
  8. //             This module contains proprietary information and should be 
  9. //                treated as confidential.
  10. //
  11. //----------------------------------------------------------------------------
  12. //                           MAINTENANCE HISTORY
  13. //
  14. // $Workfile$
  15. // $Revision$
  16. //   $Author$
  17. //     $Date$
  18. //      $Log$    
  19. //
  20. //----------------------------------------------------------------------------
  21. //                             MODULE NARRATIVE
  22. //
  23. //
  24. //    This module contains compress and expand blocks of record ids.
  25. //
  26. //    Size or terminator information is not stored in the compressed data.
  27. //
  28. //    The size of the compressed data will NEVER be larger than the uncompressed
  29. //     data. However, as a worst case, it may be the same size.
  30. //
  31. //    Because the block size can be up to 8K, there obviously can not be more 
  32. //     than 8K records in a block. Therefore, the three bits of a record
  33. //     id offset are always unused.
  34. //
  35. //    Data is read as a byte stream:
  36. //        At the start of compression, the current block and offset are assumed
  37. //         passed by the caller.
  38. //        If the high bit of the byte is clear. This is a simple 0..127 offset 
  39. //         byte. The next record is in the same block at the given delta from the
  40. //         current record.
  41. //        If the high bit is set, read the next byte. The upper 2 bits of this 
  42. //         byte are flag bits. Save them and combine the least 7 bits of the 
  43. //         first byte with the least 6 bits of the second byte to form a full 13
  44. //         bit record offset. This offset may wrap within a block. Wrapping
  45. //         always takes place assuming an 8K max block size.
  46. //        An offset is 0 based if the block id was just changed or if this is
  47. //         the first record.
  48. //        The two flag bits are used as follows:
  49. //             BIT 0: A range of records is followed. The next 1/2 byte is a record
  50. //                     offset which specifies the number of records in the range.
  51. //                     A range always has at LEAST 3 records so the range count is
  52. //                     actually 'actual range length - 3'.
  53. //             BIT 1: A new record block id delta follows. The block id delta is
  54. //                     variable length and actually has an effective range of
  55. //                     +/- 2 ^ 28.
  56. //        The two flags bits are NOT mutually exclusive.
  57. //
  58. //
  59. //    The code in this module should be written entirely in C. 
  60. //    Do not use any C++ constructs.
  61. //
  62. //    This module is portable to:
  63. //        DOS 3.X+
  64. //        MS Windows 3.X+
  65. //        OS/2 2.X+
  66. //        OS/2 2.0 PM
  67. //        SCO UNIX.
  68. //
  69. //    The following compilers are supported:
  70. //        MSC 6.0A
  71. //        MSC/C++ 7.0
  72. //        Borland C++ 3.1 for DOS
  73. //        Borland C++ 1.0 for OS/2 2.X
  74. //        SCO UNIX cc
  75. //
  76. //----------------------------------------------------------------------------
  77. #include <cp.h>
  78.  
  79.  
  80. //----------------------------------------------------------------------------
  81. //   Description:    Sort routine used by qsort to sort an array of record ids.
  82. //    Parameters:    see qsort()
  83. //       Returns:    see qsort()
  84. //----------------------------------------------------------------------------
  85. static int __recidsort__(const void *pv1, const void *pv2)
  86. {
  87.     PRECID precid1 = (PRECID)pv1;
  88.     PRECID precid2 = (PRECID)pv2;
  89.  
  90.     if (precid1->lBlock > precid2->lBlock)
  91.         return 1;
  92.     else if (precid1->lBlock < precid2->lBlock)
  93.         return -1;
  94.     else
  95.         {
  96.        if (precid1->usOffset > precid2->usOffset)
  97.            return 1;
  98.        else if (precid1->usOffset < precid2->usOffset)
  99.            return -1;
  100.         }
  101.     return 0;
  102. }
  103.  
  104.  
  105. //----------------------------------------------------------------------------
  106. //   Description:    Decode a compressed array of record ids.
  107. //    Parameters:    precid        Pointer to buffer for record ids.
  108. //                        cRec            Size of record id buffer.
  109. //                        pb                Compressed data.
  110. //                        cb                Size of compressed data.
  111. //                        pcb            Variable to recieve number of record ids.
  112. //       Returns:    TRUE if successful.
  113. //----------------------------------------------------------------------------
  114. BOOL FN_E RecIdDecode(PRECID precid, SIZET cRecs, PBYTE pb, SIZET cb, PSIZET pcb, PRECID precidBase)
  115. {
  116.     RECID recid;
  117.     BYTE b1, b2, b3, b4;
  118.     USHORT us, usOffset, usDelta;
  119.     LONG lDelta;
  120.     SIZET cDecode;
  121.     BOOL fBlockChange, fRange;
  122.  
  123.     Assert(precid && cRecs);                // Validate parameters
  124.     Assert(pb && cb);
  125.     Assert(pcb);
  126.  
  127.     cDecode = 0;                                // Initialize variables
  128.     *pcb = cDecode;
  129.  
  130.     recid.lBlock = 0;                            // Read initial record id
  131.     recid.usOffset = 0;
  132.     if (precidBase)
  133.         recid = *precidBase;
  134.  
  135.     while (cb)                                    // While there is still data left
  136.         {                                            //  to decode
  137.         b1 = *pb++;                                // Read byte
  138.         cb--;
  139.         if (b1 & 0x80)                            // If another byte is continued, read it
  140.             {
  141.             if (!cb)
  142.                 return FALSE;
  143.             b2 = *pb++;
  144.             cb--;
  145.             }
  146.         else
  147.             b2 = 0;
  148.                                                     // Compute offset
  149.         usOffset = (USHORT)((((USHORT)b2 & 0x007F) << 6) + ((USHORT)b1 & 0x003F));
  150.         fBlockChange = (b1 & 0x40) != 0;
  151.         fRange = (b2 & 0x80) != 0;
  152.         if (fBlockChange)                        // Block change
  153.             {
  154.             recid.usOffset = 0;
  155.  
  156.             if (!cb)
  157.                 return FALSE;
  158.             b1 = *pb++;
  159.             b2 = 0;
  160.             b3 = 0;
  161.             b4 = 0;
  162.             cb--;
  163.             if (b1 & 0x80)
  164.                 {
  165.                 if (!cb)
  166.                     return FALSE;
  167.                 b2 = *pb++;
  168.                 cb--;
  169.                 if (b2 & 0x80)
  170.                     {
  171.                     if (!cb)
  172.                         return FALSE;
  173.                     b3 = *pb++;
  174.                     cb--;
  175.                     if (b3 & 0x80)
  176.                         {
  177.                         if (!cb)
  178.                             return FALSE;
  179.                         b4 = *pb++;
  180.                         cb--;
  181.                         }
  182.                     }
  183.                 }
  184.             lDelta = ((LONG)b4 << 20) + ((LONG)(b3 & 0x7F) << 13)
  185.                 + ((LONG)(b2 & 0x7F) << 6) + (LONG)(b1 & 0x3F);
  186.             if (b1 & 0x40)
  187.                 lDelta = -lDelta;
  188.  
  189.             recid.lBlock += lDelta;            // Read new block and reset offset
  190.             }
  191.         if (fRange)                                // Block range specifier
  192.             {
  193.             if (!cb)                                // Read byte
  194.                 return FALSE;
  195.             b1 = *pb++;
  196.             cb--;
  197.             if (b1 & 0x80)                        // Read continuation if specified
  198.                 {
  199.                 if (!cb)
  200.                     return FALSE;
  201.                 b2 = *pb++;
  202.                 cb--;
  203.                 }
  204.             else
  205.                 b2 = 0;
  206.                                                     // Calculate # of records in range
  207.             usDelta = (USHORT)(((((USHORT)b2 & 0x003F) << 7) + ((USHORT)b1 &0x007F)) + 3);
  208.             }
  209.         else
  210.             usDelta = 1;                        // Else a single record
  211.  
  212.         recid.usOffset += usOffset;        // Build expanded record id list
  213.         if (recid.usOffset >= 8192)
  214.             recid.usOffset -= 8192;
  215.         for (us = 0; us < usDelta; us++)
  216.             {
  217.             if (!cRecs)                            // No more space for record ids
  218.                 return FALSE;
  219.             if (us)
  220.                 recid.usOffset++;
  221.             *precid = recid;
  222.             precid++;
  223.             cRecs--;
  224.             cDecode++;
  225.             }
  226.         }
  227.     if (precidBase)
  228.         *precidBase = recid;
  229.     *pcb = cDecode;                            // Return number of decoded records
  230.     return TRUE;
  231. }
  232.  
  233.  
  234. //----------------------------------------------------------------------------
  235. //   Description:    Compress an array of record ids.
  236. //    Parameters:    precid        Array of record ids
  237. //                        cRec            Number of record ids.
  238. //                        pb                Buffer for compressed data
  239. //                        cb                Size of compressed data buffer.
  240. //                        pcb            Variable to recieve size of compressed data.
  241. //                        Record id list is sorted an de-dup'ed at exit!
  242. //       Returns:    TRUE if successful.
  243. //----------------------------------------------------------------------------
  244. BOOL FN_E RecIdEncode(PRECID precid, SIZET cRecs, PBYTE pb, SIZET cb, PSIZET pcb, PRECID precidBase)
  245. {
  246.     SIZET i, j;
  247.     PRECID precid1, precid2;
  248.     RECID recid;
  249.     BYTE b1, b2, b3, b4;
  250.     LONG lDelta;
  251.     USHORT usDelta;
  252.     SIZET cEncode;
  253.     BOOL fBlockChange;
  254.  
  255.     Assert(precid && cRecs);                // Validate parameters
  256.     Assert(pb && cb);
  257.     Assert(pcb);
  258.  
  259.     cEncode = 0;                                // Initialize variables
  260.     *pcb = cEncode;
  261.  
  262.     recid.lBlock = 0;                            // Get user defined starting recid
  263.     recid.usOffset = 0;
  264.     if (precidBase)
  265.         recid = *precidBase;
  266.                                                     // Sort records
  267.     qsort(precid, cRecs, sizeof(RECID), __recidsort__);
  268.     precid1 = precid;                            // Remove duplicate records
  269.     precid2 = precid1 + 1;
  270.     j =  cRecs;
  271.     for (i = 1; i < j; i++, precid2++)
  272.         {                                // Skip duplicate record
  273.         if (precid1 != precid2
  274.         && precid1->lBlock == precid2->lBlock
  275.         && precid1->usOffset == precid2->usOffset)
  276.             {
  277.             cRecs--;
  278.             }
  279.         else                                        // Copy unique records
  280.             {
  281.             precid1++;
  282.             if (precid1 != precid2)
  283.                 *precid1 = *precid2;
  284.             }
  285.         }
  286.     while (cRecs)                                // While records to compress, keep working
  287.         {
  288.         for (i = 1; i < cRecs; ++i)        // Search for a range of records
  289.             if (precid[i-1].lBlock != precid[i].lBlock
  290.             || precid[i-1].usOffset + 1 != precid[i].usOffset)
  291.                 break;
  292.                                                     // Check if block is changing
  293.         fBlockChange = (precid[0].lBlock != recid.lBlock);
  294.         if (fBlockChange)                        // Reset starting offset on block change
  295.             {
  296.             recid.usOffset = 0;
  297.             lDelta = precid[0].lBlock - recid.lBlock;
  298.             }
  299.                                            // Calculate delta MOD 8192     
  300.         if (recid.usOffset > precid[0].usOffset)
  301.             usDelta =  (USHORT)(8192 - (recid.usOffset - precid[0].usOffset));
  302.         else
  303.             usDelta = (USHORT)(precid[0].usOffset - recid.usOffset);
  304.         Assert(usDelta < 8192);
  305.  
  306.         b1 = (BYTE)(usDelta & 0x003F);    // Break into bytes
  307.         b2 = (BYTE)((usDelta >> 6) & 0x007F);
  308.         if (i >= 3)                                // Record range
  309.             b2 |= 0x80;
  310.         if (fBlockChange)                        // Block id has changed
  311.             b1 |= 0x40;
  312.         if (b2)                                    // Set continuation bit if second
  313.             b1 |= 0x80;                            //  byte is non-zero
  314.         if (!cb)                                    // Output offset
  315.             return FALSE;
  316.         *pb++ = b1;
  317.         cb--;
  318.         cEncode++;
  319.         if (b1 & 0x80)                            // Output continuation
  320.             {
  321.             if (!cb)
  322.                 return FALSE;
  323.             *pb++ = b2;
  324.             cb--;
  325.             cEncode++;
  326.             }                                        // Output block change
  327.         if (fBlockChange)
  328.             {
  329.             BOOL fMinus;
  330.  
  331.             if (lDelta < 0)
  332.                 {
  333.                 lDelta = -lDelta;
  334.                 fMinus = TRUE;
  335.                 }
  336.             else
  337.                 fMinus = FALSE;
  338.             Assert((lDelta & 0x80000000L) == 0);
  339.  
  340.             b1 = (BYTE)(lDelta & 0x3F);
  341.             b2 = (BYTE)((lDelta >> 6) & 0x7F);
  342.             b3 = (BYTE)((lDelta >> 13) & 0x7F);
  343.             b4 = (BYTE)((lDelta >> 20) & 0xFF);
  344.             if (b4)
  345.                 b3 |= 0x80;
  346.             if (b3)
  347.                 b2 |= 0x80;
  348.             if (b2)
  349.                 b1 |= 0x80;
  350.             if (fMinus)
  351.                 b1 |= 0x40;
  352.  
  353.             if (!cb)
  354.                 return FALSE;
  355.             *pb++ = b1;
  356.             cb--;
  357.             cEncode++;
  358.             if (b2)
  359.                 {
  360.                 if (!cb)
  361.                    return FALSE;
  362.                *pb++ = b2;
  363.                cb--;
  364.                cEncode++;
  365.                 }
  366.             if (b3)
  367.                 {
  368.                if (!cb)
  369.                    return FALSE;
  370.                *pb++ = b3;
  371.                cb--;
  372.                cEncode++;
  373.                 }
  374.             if (b4)
  375.                 {
  376.                if (!cb)
  377.                    return FALSE;
  378.                *pb++ = b3;
  379.                cb--;
  380.                cEncode++;
  381.                 }
  382.             }
  383.         if (i >= 3)                                // Output range if specified
  384.             {
  385.             usDelta = (USHORT)(i - 3);
  386.             b1 = (BYTE)(usDelta & 0x007F);
  387.             b2 = (BYTE)((usDelta >> 7) & 0x003F);
  388.             if (!cb)
  389.                 return FALSE;
  390.             *pb++ = b1;
  391.             cb--;
  392.             cEncode++;
  393.             if (b1 & 0x80)
  394.                 {
  395.                 if (!cb)
  396.                     return FALSE;
  397.                 *pb++ = b2;
  398.                 cb--;
  399.                 cEncode++;
  400.                 }
  401.             }
  402.         else
  403.             i = 1;
  404.         cRecs -= i;                                // Move pointers
  405.         precid += i;
  406.         recid = *(precid - 1);                // Store a copy of the last record id
  407.         }
  408.     if (precidBase)
  409.         *precidBase = recid;
  410.     *pcb = cEncode;
  411.     return TRUE;
  412. }
  413.  
  414.  
  415. //----------------------------------------------------------------------------
  416. //   Description:    Run standard test suite
  417. //    Parameters:    sTest        Test to run.
  418. //                                        0        Run all default tests (except).
  419. //       Returns:    TRUE if successful.
  420. //----------------------------------------------------------------------------
  421. #if COMPILE_TEST
  422. BOOL FN RecIdTest(SHORT sTest)
  423. {
  424. static RECID arecid[][20] =
  425.     {
  426.     {{ 0, 0},{ 0, 1},{ 0, 3},{ 1, 0},{ 2, 0},{ 3, 0},{ 4, 0},{-1, -1}},
  427.     {{ 0, 0},{ 1, 1},{ 1, 2},{ 1, 3},{ 2, 0},{ 2, 1},{ 2, 2},{ 2, 3},{-1, -1}},
  428.     {{ 0, 1},{ 0, 0},{ 0, 0},{ 2, 0},{ 2, 0},{ 2, 0},{ 3, 0},{-1, -1}},
  429.     {{ 0, 0},{ 0, 127},{ 0, 128},{ 0, 1024},{-1, -1}},
  430.     {{ 0, 10},{-1, -1}},
  431.     {{ 0, 9},{-1, -1}},
  432.     {{ 0, 9},{-1, -1}},
  433.     {{ 1, 0},{-1, -1}},
  434.     {{ 9999998L, 0},{-1, -1}},
  435.     {{ 9999999L, 0},{-1, -1}},
  436.     {{ 1111111L, 0},{-1, -1}},
  437.     {{ 1111110L, 0},{-1, -1}},
  438.     {{-1, -1}}
  439.     };
  440.  
  441. static RECID arecidDecode[100];
  442. static BYTE bBuf[4 * 100];
  443.     SIZET cb;
  444.     SIZET cRecs;
  445.     SIZET i, j, k;
  446.     RECID recid1, recid2;
  447.  
  448.  
  449.     NOTUSED(sTest);
  450.     recid1.lBlock = 0;
  451.     recid1.usOffset = 0;
  452.     recid2.lBlock = 0;
  453.     recid2.usOffset = 0;
  454.     for (i = 0; arecid[i][0].lBlock != -1; ++i)
  455.         {
  456.         for (j = 0; arecid[i][j].lBlock != -1; ++j)
  457.             ;
  458.         if (!RecIdEncode(&arecid[i][0], j, bBuf, sizeof(bBuf), &cb, &recid1))
  459.             return FALSE;
  460.  
  461.         Output("Record Set # %u\n", i+1);
  462.         Output("  %2d input records encoded into %u bytes.\n", j, cb);
  463.                                                     // Count after de-dup
  464.         for (k = 0; arecid[i][k].lBlock != -1; ++k)
  465.             if (k > 0
  466.             && (arecid[i][k].lBlock < arecid[i][k - 1].lBlock
  467.             || (arecid[i][k].lBlock == arecid[i][k - 1].lBlock
  468.             && arecid[i][k].usOffset <= arecid[i][k - 1].usOffset)))
  469.                 break;
  470.  
  471.         if (!RecIdDecode(&arecidDecode[0], 100, bBuf, cb, &cRecs, &recid2))
  472.             return FALSE;
  473.  
  474.         Output("  %2d output records.\n", cRecs);
  475.  
  476.         if (cRecs != k                            // Check data
  477.         || memcmp(arecid[i], arecidDecode, cRecs) != 0)
  478.             return FALSE;
  479.         }
  480.     return TRUE;
  481. }
  482. #endif
  483. //----------------------------------------------------------------------------
  484. //------------------------------- End of File --------------------------------
  485. //----------------------------------------------------------------------------
  486.